package org.copper.utils
{
	/**
	 * Utility for string analysis.
	 * */
	public final class LCSutility
	{
		/**
		 * Calculates percentage of difference between 2 given strings.
		 * Returned number between 0 and 1.
		 * 0 - if strings are equal.
		 * 1 - if strings are completely different.
		 */
		public static function compareStrings(a:String, b:String):Number
		{
			if (a != null && b != null)
			{
				const aLen:int = a.length;
				const blen:int = b.length;
				const avlen:Number = (aLen + blen) * 0.5;
				const lcsLen:int = lcsLenght(a, b);
				const avDist:Number = (Math.abs(aLen - lcsLen) + Math.abs(blen - lcsLen)) * 0.5;
				return avDist/avlen;
			}
			else
			{
				if (a == null && b == null)
					return 0;
				
				return 1;
			}
		}
		
		/**
		 * Calculates first longest common sequence of 2 given strings.
		 */
		public static function lcs(x:String, y:String):String
		{
			const result:Vector.<String> = new Vector.<String>();
			const M:int = x.length
			const N:int = y.length;
			
			const opt:Vector.<Vector.<int>> = initTable(new Vector.<Vector.<int>>(), M+1, N+1);
			
			var i:int;
			var j:int;
			
			for (i = M-1; i >= 0; i--) 
			{
				for (j = N-1; j >= 0; j--) 
				{
					if (x.charAt(i) == y.charAt(j))
						opt[i][j] = opt[i+1][j+1] + 1;
					else 
						opt[i][j] = max(opt[i+1][j], opt[i][j+1]);
				}
			}
			
			i = 0;
			j = 0;
			
			
			while(i < M && j < N) 
			{
				if (x.charAt(i) == y.charAt(j)) 
				{
					result.push(x.charAt(i));
					i++;
					j++;
				}
				else 
				{
					const ni:int = i+1;
					const nj:int = j+1;
					if (opt[ni][j] > opt[i][nj]) 
					{
						i = ni;
					}
					else 
					{
						j = nj;
					}
				}
			}
			
			return result.join("");
		}
		
		
		
		/**
		 * Calculates the lenght of LCS.
		 */
		public static function lcsLenght(x:String, y:String):int
		{
			const M:int = x.length
			const N:int = y.length;
			
			const opt:Vector.<Vector.<int>> = initTable(new Vector.<Vector.<int>>(), M+1, N+1);
			
			var i:int;
			var j:int;
			
			for (i = M-1; i >= 0; i--) 
				for (j = N-1; j >= 0; j--) 
					if (x.charAt(i) == y.charAt(j))
						opt[i][j] = opt[i+1][j+1] + 1;
					else 
						opt[i][j] = max(opt[i+1][j], opt[i][j+1]);
			
			
			return opt[0][0];
		}
		
		/**
		 * If 2 there is more than one LCS in givent 2 strings - calculates all the options.
		 */
		public static function lcsAll(x:String, y:String):Vector.<String>
		{
			const result:Vector.<String> = new Vector.<String>();
			const M:int = x.length
			const N:int = y.length;
			
			const opt:Vector.<Vector.<int>> = initTable(new Vector.<Vector.<int>>(), M+1, N+1);
			
			var i:int;
			var j:int;
			
			for (i = M-1; i >= 0; i--) 
			{
				for (j = N-1; j >= 0; j--) 
				{
					if (x.charAt(i) == y.charAt(j))
						opt[i][j] = opt[i+1][j+1] + 1;
					else 
						opt[i][j] = max(opt[i+1][j], opt[i][j+1]);
				}
			}
			
			const results:Vector.<Vector.<String>> = iterateResults(opt, x, y);
			
			for each(var vec:Vector.<String> in results)
			{
				result.push(vec.join(""));
			}
			
			result.fixed = true;
			return result;
		}
		
		
		private static function iterateResults(map:Vector.<Vector.<int>>, x:String, y:String, goRight:Boolean = true, causedPair:Object = null):Vector.<Vector.<String>>
		{
			const result:Vector.<Vector.<String>> = new Vector.<Vector.<String>>();
			const collector:Vector.<String> = new Vector.<String>();
			result.push(collector);
			const M:int = x.length
			const N:int = y.length;
			var i:int = 0;
			var j:int = 0;
			
			
			while(i < M && j < N) 
			{
				if (x.charAt(i) == y.charAt(j)) 
				{
					collector.push(x.charAt(i));	
					i++;
					j++;
				}
				else 
				{
					const ni:int = i+1;
					const nj:int = j+1;
					const niv:int = map[ni][j];
					const njv:int = map[i][nj];
					if (niv == njv)
					{
						if (goRight)
						{
							i = ni;
						}
						else
						{
							j = nj;
						}
						
						var ress:Vector.<Vector.<String>>;
						var rres:Vector.<String>;
						
						if (causedPair == null)
						{
							ress = iterateResults(map, x, y, false, {ii:niv, jj:njv});
							for each(rres in ress)
							{
								result.push(rres);
							}
							
						}
						else
						{
							if (!(niv == causedPair.ii && njv == causedPair.jj))
							{
								ress = iterateResults(map, x, y, false, {ii:niv, jj:njv});
								for each(rres in ress)
								{
									result.push(rres);
								}
							}
						}
					}
					else if (niv > njv) 
					{
						i = ni;
					}
					else 
					{
						j = nj;
					}
				}
			}
			
			result.fixed = true;
			return result;
		}
		
		
		
		
		private static function initTable(opt:Vector.<Vector.<int>>, m:int, n:int):Vector.<Vector.<int>>
		{
			opt.length = m;
			opt.fixed = true;
			
			for(var i:int = 0; i < m; i++)
			{
				const vec:Vector.<int> = new Vector.<int>();
				vec.length = n;
				vec.fixed = true;
				opt[i] = vec;
			}
			
			return opt;
		}
		
		
		private static function max(a:int, b:int):int
		{
			return a > b?a:b;
		}
	}
}